package com.example.yblin.hello24;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;


class Rational {
    private long m_up;
    private long m_down;

    public Rational() {

    }

    public Rational(long up, long down) {
        super();
        // 约分
        long g = gcd(up >= 0 ? up : -up, down > 0 ? down : -down);
        this.m_up = up / g;
        this.m_down = down / g;
    }

    public long getM_up() {
        return m_up;
    }

    public long getM_down() {
        return m_down;
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public Rational add(Rational r) {
        long up = m_up * r.m_down + m_down * r.m_up;
        long down = m_down * r.m_down;
        return new Rational(up, down);
    }

    public Rational subtract(Rational r) {
        long up = m_up * r.m_down - m_down * r.m_up;
        long down = m_down * r.m_down;
        return new Rational(up, down);
    }

    public Rational multiply(Rational r) {
        long up = m_up * r.m_up;
        long down = m_down * r.m_down;
        return new Rational(up, down);
    }

    //不会有除0错误，哇哈哈哈！！！
    public Rational divide(Rational r) {
        long up = m_up * r.m_down;
        long down = m_down * r.m_up;
        return new Rational(up, down);
    }

    private static long quickPow(long a, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res *= a;
            }
            a *= a;
            n >>= 1;
        }
        return res;
    }

    public Rational pow(int n) {
        return new Rational(quickPow(m_up, n), quickPow(m_down, n));
    }

    @Override
    public String toString() {
        if (m_down < 0) {
            m_up = -m_up;
            m_down = -m_down;
        }
        return m_up + (m_down == 1 ? "" : "/" + m_down);
    }
}


public class Calculate {

    /*
     * 判断是否在给定的4个数字内
     */
    private static boolean in(ArrayList<Integer> arrayList, int num1, int num2, int num3, int num4) {
        if (arrayList.size() != 4) {
            return false;
        }
        Collections.sort(arrayList);
        int[] tmp = new int[]{num1, num2, num3, num4};
        Arrays.sort(tmp);
        for (int i = 0; i < 4; i++) {
            if (tmp[i] != arrayList.get(i)) {
                return false;
            }
        }
        return true;
    }

    /*
     * 判断是否是数字
     */
    private static boolean isNum(String exp, int pos) {
        char ch = exp.charAt(pos);
        return ch >= '0' && ch <= '9';
    }

    /*
     * 给定运算符的优先级
     */
    private static int count(char c) {
        if (c == '=')
            return 0;
        if (c == '(')
            return 1;
        if (c == '+')
            return 2;
        if (c == '-')
            return 3;
        if (c == '*')
            return 4;
        if (c == '/')
            return 5;
        if (c == '^')
            return 6;
        return 7;
    }


    /*
     * 将所给表达式转换为后缀表达式
     */
    private static String trans(String exp) {

        // 负数都用括号括起来
        for (int i = 0; i < exp.length(); i++) {
            if (exp.charAt(i) == '-' && exp.charAt(i - 1) == '(') {
                exp = exp.substring(0, i) + '0' + exp.substring(i, exp.length());
                i++;
            }
        }
        // System.out.println(exp);

        String postexp = "";
        int lpri[] = { 0, 1, 3, 3, 5, 5, 7, 8 }; // =(+-*/^)
        int rpri[] = { 0, 8, 2, 2, 4, 4, 6, 1 };

        ArrayList<Character> op = new ArrayList<>();

        op.add('=');
        for (int i = 0; i < exp.length();) {
            if (isNum(exp, i)) {
                while (i < exp.length() && isNum(exp, i)) {
                    postexp += exp.charAt(i);
                    i++;
                }
                postexp += '#';
            } else {
                if (lpri[count(op.get(op.size() - 1))] < rpri[count(exp.charAt(i))]) {
                    op.add(exp.charAt(i));
                    i++;
                } else if (lpri[count(op.get(op.size() - 1))] == rpri[count(exp.charAt(i))]) {
                    op.remove(op.size() - 1);
                    i++;
                } else {
                    postexp += op.get(op.size() - 1);
                    op.remove(op.size() - 1);
                }
            }
        }

        while (!op.isEmpty() && op.get(op.size() - 1) != '=') {
            postexp += op.get(op.size() - 1);
            op.remove(op.size() - 1);
        }

        return postexp;
    }



    /*
     * true 表示答案正确
     * false 表示答案错误
     * null 表示非法表达式
     */
    public static Boolean returnAnswer(String s, int num1, int num2, int num3, int num4) {
        //将数字提取出来，如果有不在给定数字中的，直接返回非法表达式
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < s.length(); ) {
            if (s.charAt(i) > '0' && s.charAt(i) <= '9') {
                int j = i, num = 0;
                for (; j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9'; j++) {
                    num = num * 10 + s.charAt(j) - '0';
                }
                arrayList.add(num);
                i = j;
            } else {
                i++;
            }
        }
        if (!in(arrayList, num1, num2, num3, num4)) {
            return null;
        }
        //表达式非法，括号不匹配，或者出现连续的运算符
        Rational res;
        try {
            res = calc(trans(s));
        } catch (Exception e) {
            return null;
        }

        return res != null && res.getM_up() == 24 && res.getM_down() == 1;
    }




    //模块二：计算表达式的值
    private static Rational calc(String postexp) throws Exception {
        ArrayList<Rational> st = new ArrayList<>();
        for (int i = 0; i < postexp.length();) {
            switch (postexp.charAt(i)) {
                case '+':
                    Rational r1 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    Rational r2 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    st.add(r1.add(r2));
                    break;
                case '-':
                    r1 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    r2 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    st.add(r2.subtract(r1));
                    break;
                case '*':
                    r1 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    r2 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    st.add(r1.multiply(r2));
                    break;
                case '/':
                    r1 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    r2 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    st.add(r2.divide(r1));
                    break;
                case '^':
                    r1 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    r2 = st.get(st.size() - 1);
                    st.remove(st.size() - 1);
                    st.add(r2.pow((int) r1.getM_up()));
                    break;
                case '(':
                case ')':
                    throw new Exception();
                default:
                    long num = 0;
                    while (i < postexp.length() && isNum(postexp, i)) {
                        num = num * 10 + postexp.charAt(i) - '0';
                        i++;
                    }
                    st.add(new Rational(num, 1));
                    break;
            }
            i++;
        }
        return st.get(st.size() - 1);
    }



    public static void main(String[] arg) throws Exception {
        System.out.println(returnAnswer("6+6+6+6", 6, 6, 6, 5));

    }
}